package sword.offer;

/**
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的
 *
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class TwentyFive {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        Solution solution = new Solution();
        ListNode listNode = solution.mergeTwoLists(l1, l2);
        while(listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
    /**
     * 将第二个链表合并到第一个链表中
     * 定义两个指针  分别指向两个链表的头结点，判断第二个指针指向的元素是否小于等于 第一个指针指向的元素
     * 如果小于 那么将第二个指针指向的元素插入到 第一个指针的前面。
     * 所以我们需要一个指针指向 第一个指针的前驱结点
     * 所以就需要一个<b>伪结点</b>
     * <p></p>
     * 为什么是小于等于呢？
     * 我们可以举一个例子 <br/>
     * 当l1为 1 2 3  <br/>
     *  l2 为 4 5 6
     * 那么当l2>=l1就插入到l1.next 那么就会将l2的第一个元素4 插入到l1的第一个元素之后，很显然这样是不对的
     * */
    static class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode dum = new ListNode(0);
            dum.next = l1;
            ListNode cur = dum;
            while (l1 != null && l2 != null){
                if(l1.val >= l2.val){
                    cur.next = l2;
                    l2 = l2.next;
                }else{
                    cur.next = l1;
                    l1 = l1.next;
                }
                cur = cur.next;
            }
            cur.next = l1 != null ? l1 : l2;
            return dum.next;
        }
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
